/*
 * @Author: 缄默
 * @Date: 2022-01-06 20:35:39
 * @LastEditors: 缄默
 * @LastEditTime: 2022-01-06 20:56:06
 */

//排成一条线的纸牌博弈问题

#include <iostream>
#include <vector>

using namespace std;

int win1(vector<int>& arr, int left, int right, int sum);

int main() {
    vector<int> arr({1, 2, 100, 4});
    int sum;
    for (auto x : arr) {
        sum += x;
    }
    cout << win1(arr, 0, arr.size() - 1, sum) << endl;
    return 0;
}

//时间复杂度o（2的n方）
int win1(vector<int>& arr, int left, int right, int sum) {
    if (left == right) return arr[left];
    int l1 = sum - win1(arr, left + 1, right, sum - arr[left]);
    int r1 = sum - win1(arr, left, right - 1, sum - arr[right]);
    return l1 < r1 ? r1 : l1;

}